public class Sort {


    /**
     * 不稳定的
     * 时间复杂度：n^1.3  - n^1.5
     * 空间复杂度：O(1)
     * @param array
     */

    //希尔排序就是直接插入排序的优化版本
    //核心思想是缩小增量排序
    public static void ShellSort(int[] array) {
        int gap = array.length;

        //gap的取值可以变化
        //gap 大于 1 之前都称为 预排序
        while(gap > 1) {
            gap = gap / 2;
            shell(array,gap);
        }
    }

    public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int ret = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                //如果不拿 ret 接收 array[i] 的而是直接使用 array[i] ，
                // 就会有array[j + gap] = array[j];把array[i]覆盖的风险，array[i] 的值会发生变化
                if(array[j] > ret) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = ret;
        }
    }
}
